#ifndef RAIS_GRAPH_H
#define RAIS_GRAPH_H

#include "Rais_LinkedList.h"

namespace rais{
	
using venum_t = unsigned char;

//Vertex: 图结构端点基类, 存储一个无向图.
class Vertex {
	public:
	venum_t index = 0;
	Vertex** es = nullptr;
	
	
	void init(venum_t idx, venum_t max_e_num){
		index = idx;
		if(!max_e_num) return;
		es = new Vertex*[max_e_num];
		for(venum_t i = 0; i < max_e_num; ++i) es[i] = nullptr;
	}
	
	Vertex(venum_t idx, venum_t max_e_num){init(idx, max_e_num); }
	Vertex(){}
	~Vertex(){
		delete[] es;
		es = nullptr;
	}
	
	
	void setE(venum_t e_idx, Vertex& adj_v){
		es[e_idx] = &adj_v;
	}
	void setE(venum_t e_idx, Vertex* adj_vp){
		es[e_idx] = adj_vp;
	}
	
};
static const Vertex& ERROR_VERTEX = Vertex(-1, 0);


//Graph: 图结构基类
template <typename VT = Vertex> //VT is type of graph's vertex
class Graph{
	protected:
	
	venum_t v_num = 0;              //the number of vertex
	venum_t e_num = 0;              //the number of vertex's edge
	VT* vs = nullptr;               //vertexes data
	
	public:
	using graph_builderfp_t = void(*)(Graph<VT>&);

	Graph(venum_t pv_num, venum_t pe_num): v_num(pv_num), e_num(pe_num) {
		if(!v_num) return;
		vs = new VT[v_num];
		for(venum_t i = 0; i < v_num; ++i) vs[i].init(i, e_num);
	} 
	Graph(venum_t pv_num, venum_t pe_num, const graph_builderfp_t builder): Graph(pv_num, pe_num){
		if(builder != nullptr) builder(*this);
	}
	Graph(const Graph<VT>& g): Graph(g.v_num, g.e_num){
		for(venum_t v_idx = 0; v_idx < v_num; ++v_idx)
			for(venum_t e_idx = 0; e_idx < e_num; ++e_idx)
				vs[v_idx].setE(e_idx, vs[g.vs[v_idx].es[e_idx]->index]);
	}
	Graph(Graph<VT>&& g){
		if(!g.v_num) return;
		v_num = g.v_num;
		e_num = g.e_num;
		vs = g.vs;
		g.vs = nullptr;
	}
	Graph<VT>& operator=(const Graph<VT>& g){
		if(this != &g)
			for(venum_t v_idx = 0; v_idx < v_num; ++v_idx)
				for(venum_t e_idx = 0; e_idx < e_num; ++e_idx)
					vs[v_idx].setE(e_idx, vs[g.vs[v_idx].es[e_idx]->index]);
		return *this;
	}
	Graph<VT>& operator=(Graph<VT>&& g){
		if(this != &g) {
			delete[] vs;
			v_num = g.v_num;
			e_num = g.e_num;
			vs = g.vs;
			g.vs = nullptr;
		}
		return *this;
	}
	
	~Graph(){
		if(vs == nullptr) return;
		delete[] vs;
		vs = nullptr;
		v_num = 0;
		e_num = 0;
	}
	
						  
 
	//linking two vertexes
	bool link(VT& host, VT& adj, venum_t host_e_idx, venum_t adj_e_idx){
		if(host_e_idx >= e_num || adj_e_idx >= e_num) return false;
		host.setE(host_e_idx, adj);
		adj.setE(adj_e_idx, host);
		return true;
	}
	bool link(venum_t host_idx, venum_t adj_idx, venum_t host_e_idx, venum_t adj_e_idx){
		if(host_idx >= v_num || adj_idx >= v_num) return false;
		return link(vs[host_idx], vs[adj_idx], host_e_idx, adj_e_idx);
	}
	
	template <typename... VTs>
	bool links(venum_t host_e_idx, venum_t adj_e_idx, VT& v1, VT& v2, VTs&... vn){
		if(host_e_idx >= e_num || adj_e_idx >= e_num) return false;
		return linking(host_e_idx, adj_e_idx, v1, v2, vn...);
	}
	template <typename... VIDX_Ts>
	bool links(venum_t host_e_idx, venum_t adj_e_idx, venum_t v1_idx, venum_t v2_idx, VIDX_Ts... vn_idx){
		if(host_e_idx >= e_num || adj_e_idx >= e_num) return false;
		return links(host_e_idx, adj_e_idx, v1_idx , v2_idx, vn_idx...);
	}
	
	//cutting two adjacent vertexes
	bool cut(VT& host, venum_t e_idx){
		if(e_idx >= e_num) return false;
		VT* adj = host.es[e_idx];
		if(adj != nullptr){
			host.setE(e_idx, nullptr);
			for(venum_t i = 0; i < e_num; ++i){
				if(adj->es[i] == &host){
					adj->setE(i, nullptr);
					return true;
				}
			}
		}
		return true;
	}
	bool cut(venum_t host_idx, venum_t e_idx){
		if(host_idx >= v_num) return false;
		return cut(vs[host_idx], e_idx);
	}
	
	VT& getV(venum_t idx){
		if(idx >= v_num) return const_cast<VT&>(ERROR_VERTEX);
		return vs[idx];
	}

	venum_t getVNum() const{return v_num;}
	venum_t getENum() const{return e_num;}
	
	venum_t getVIndex(const VT& v) const{
		if(v.index < v_num && &getV(v.index) == &v) return v.index;
		else return v_num;
	}
	
	//get adj's index in host's es array
	venum_t getEIndex(const VT& host, const VT& adj) const{
		if(&host == &ERROR_VERTEX || &adj == &ERROR_VERTEX) return e_num;
		for(venum_t i = 0; i < e_num; ++i){
			if(host.es[i] == &adj) return i;
		}
		return e_num;	//host and adj is not adjacency
	}
	venum_t getEIndex(venum_t host_idx, venum_t adj_idx) const{
		if(host_idx >= v_num || adj_idx >= v_num) return e_num;
		for(venum_t i = 0; i < e_num; ++i){
			if(vs[host_idx].es[i] == &vs[adj_idx]) return i;
		}
		return e_num;
	}
	
	static bool isError(const VT& v){
		return &v == &const_cast<VT&>(ERROR_VERTEX);
	}
	bool isError(venum_t v_idx) const{
		return v_idx >= v_num;
	}
	
	protected:
	template <typename... VTs>
	bool linking(venum_t host_e_idx, venum_t adj_e_idx, VT& v1, VT& v2, VTs&... vn){
		v1.setE(host_e_idx, v2);
		v2.setE(adj_e_idx, v1);
		return linking(host_e_idx, adj_e_idx, v2, vn...);
	}
	template <typename... VIDX_Ts>
	bool linking(venum_t host_e_idx, venum_t adj_e_idx, venum_t v1_idx, venum_t v2_idx, VIDX_Ts... vn_idx){
		if(v1_idx >= v_num || v2_idx >= v_num) return false;
		vs[v1_idx].setE(host_e_idx, vs[v2_idx]);
		vs[v2_idx].setE(adj_e_idx, vs[v1_idx]);
		return linking(host_e_idx, adj_e_idx, v2_idx, vn_idx...);
	}
	
	//recursion end
	template <typename T>
	bool linking(venum_t host_e_idx, venum_t adj_e_idx, T&& v_or_vidx){
		static_cast<void>(host_e_idx);
		static_cast<void>(adj_e_idx);
		static_cast<void>(v_or_vidx);
		
		return true;
	}

};

//OrthogonalGraph: 正交图结构基类, 继承自Graph
//该图结构规定了每个端点有四个方向(北东南西), 且北方与南方相反向, 东方与西方相反向. 

enum O_Direction: unsigned char{
	//正交图结构方向(编号以顺时针顺序):
	O_NORTH = 0,	//北
	O_EAST  = 1,	//东
	O_SOUTH = 2,	//南
	O_WEST  = 3,	//西
	O_NONE  = 4		//无方向
};

//反转方向: make 0<-->2, 1<-->3
#define REVERSED_IDX(idx) ((idx) ^ 2)

template <typename VT = Vertex>
class OrthogonalGraph: public Graph<VT>{
	protected:
	//It's necessary for derived class template with g++ compiler:
	using Graph<VT>::v_num;
	using Graph<VT>::e_num;
	using Graph<VT>::vs;
	
	using ograph_builderfp_t = void(*)(OrthogonalGraph<VT>&);
	
	public:
	
	OrthogonalGraph(venum_t pv_num, const ograph_builderfp_t builder = nullptr): Graph<VT>(pv_num, 4){
		if(builder != nullptr) builder(*this);
	}
	OrthogonalGraph(const OrthogonalGraph<VT>& g): OrthogonalGraph(g){
		for(venum_t v_idx = 0; v_idx < v_num; ++v_idx)
			for(venum_t e_idx = 0; e_idx < 4; ++e_idx)
				vs[v_idx].setE(e_idx, vs[g.vs[v_idx].es[e_idx]->index]);
	}
	OrthogonalGraph(OrthogonalGraph<VT>&& g){
		if(!g.v_num) return;
		v_num = g.v_num;
		e_num = 4;
		vs = g.vs;
		g.vs = nullptr;
	}
	OrthogonalGraph<VT>& operator=(const OrthogonalGraph<VT>& g){
		Graph<VT>::operator=(g);
		return *this;
	}
	OrthogonalGraph<VT>& operator=(OrthogonalGraph<VT>&& g){
		if(this != &g) {
			delete[] vs;
			v_num = g.v_num;
			vs = g.vs;
			g.vs = nullptr;
		}
		return *this;
	}
	
	//linking two vertexes
	bool link(VT& host, VT& adj, venum_t e_idx){
		return Graph<VT>::link(host, adj, e_idx, REVERSED_IDX(e_idx));
	}
	bool link(venum_t host_idx, venum_t adj_idx, venum_t e_idx){
		return Graph<VT>::link(host_idx, adj_idx, e_idx, REVERSED_IDX(e_idx));
	}
	
	template <typename... VTs>
	bool links(venum_t host_e_idx, VT& v1, VT& v2, VTs&... vn){
		if(host_e_idx >= e_num) return false;
		return Graph<VT>::linking(host_e_idx, REVERSED_IDX(host_e_idx), v1, v2, vn...);
	}
	template <typename... VIDX_Ts>
	bool links(venum_t host_e_idx, venum_t v1_idx, venum_t v2_idx, VIDX_Ts... vn_idx){
		if(host_e_idx >= e_num) return false;
		return Graph<VT>::linking(host_e_idx, REVERSED_IDX(host_e_idx), v1_idx, v2_idx, vn_idx...);
	}
	
	//cutting two adjacent vertexes
	bool cut(VT& host, venum_t e_idx){
		if(e_idx >= e_num) return false;
		host.es[e_idx]->setE(REVERSED_IDX(e_idx), nullptr);
		host.setE(e_idx, nullptr);
		return true;
	}
	bool cut(venum_t host_idx, venum_t e_idx){
		if(host_idx >= v_num) return false;
		return cut(vs[host_idx], e_idx);
	}
	
	//get adj's index in host's es array - static version
	static venum_t getEIndex_static(const VT& host, const VT& adj){
		if(&host == &ERROR_VERTEX || &adj == &ERROR_VERTEX) return 4;
		for(venum_t i = 0; i < 4; ++i){
			if(host.es[i] == &adj) return i;
		}
		return 4;	//host and adj is not adjacency
	}
	
};

//PathFinder: 图结构寻路算法


//寻路结果状态量:
enum FindingResult: unsigned char{
	FOUND            = 0,  //找到路径
	HASN_FOUND       = 1,  //未调用 find() 函数
	UNREACHABLE_DEST = 2,  //不可到达的目的地
	NULL_GRAPH       = 3,  //空的图结构
	NULL_START       = 4,  //空的起点
	NULL_DEST        = 5,  //空的目的地
	OTHER            = 6,  //其他
};

//I have no choice but to use macro... sometimes it must be a literal...
#define FINDING_RESULT_EXPLAIN_0 "Successfully found a path."
#define FINDING_RESULT_EXPLAIN_1 "Hasn\'t call \'find()\' method."
#define FINDING_RESULT_EXPLAIN_2 "The destination is unreachable."
#define FINDING_RESULT_EXPLAIN_3 "Hasn\'t set graph or the graph don\'t have any vertex."
#define FINDING_RESULT_EXPLAIN_4 "Hasn\'t set start point."
#define FINDING_RESULT_EXPLAIN_5 "Hasn\'t set destination."


template <typename VT = Vertex>
class PathFinder{
	protected:
	VT* start = nullptr;	//starting point
	VT* dest  = nullptr;	//destination
	
	Graph<VT>* graph = nullptr;
	FindingResult result = FindingResult::HASN_FOUND;
	
	public:
	LinkedList<VT&> path;	//path from [start to dest]
	
	PathFinder(Graph<VT>& g){setGraph(g);}
	PathFinder(){}

	
	void setGraph(Graph<VT>& g){
		if(graph != nullptr) {
			path.clear();
			start = nullptr;
			dest = nullptr;
			result = FindingResult::HASN_FOUND;
		}
		graph = &g;
	}
	
	void setStart(VT& v){
		start = &v;
		result = FindingResult::HASN_FOUND;
	}
	void setStart(venum_t v_idx){
		if(graph == nullptr || v_idx >= graph->getVNum()) return;
		start = &graph->getV(v_idx);
		result = FindingResult::HASN_FOUND;
	}
	
	void setDest(VT& v){
		dest = &v;
		result = FindingResult::HASN_FOUND;
	}
	void setDest(venum_t v_idx){
		if(graph == nullptr || v_idx >= graph->getVNum()) return;
		dest = &graph->getV(v_idx);
		result = FindingResult::HASN_FOUND;
	}
	
	VT& getStart() const{
		if(start == nullptr) return const_cast<VT&>(ERROR_VERTEX);
		return *start;
	}
	VT& getDest() const{
		if(dest == nullptr) return const_cast<VT&>(ERROR_VERTEX);
		return *dest;
	}
	
	//return a reference is not a good idea, because the pointer of graph maght be a nullptr.
	Graph<VT>* getGraphPtr() const{return graph;}
	
	FindingResult getResult() const{return result;}
	
	virtual FindingResult find(){
		path.clear();
		if(graph == nullptr || graph->getVNum() == 0){
			result = FindingResult::NULL_GRAPH;
			return result;
		}
		if(start == nullptr){
			result = FindingResult::NULL_START;
			return result;
		}
		if(dest == nullptr){
			result = FindingResult::NULL_DEST;
			return result;
		} 
		if(start == dest){
			path.push(*start);
			result = FindingResult::FOUND;
			return result;
		}
		
		
		LinkedList<VT&> searchQue;
		VT** visiter = new VT*[graph->getVNum()];
		for(venum_t i = 0; i < graph->getVNum(); ++i) visiter[i] = nullptr;
		bool found = false;

		visiter[start->index] = &const_cast<VT&>(ERROR_VERTEX);
		searchQue.push(*start);
		while(true){
			if(searchQue.getLength() == 0 || found) break;
			found = BFS(searchQue.shift(), visiter, searchQue);
		}
		
		if(found){
			VT* bktracking_p = dest;
			while(bktracking_p != &const_cast<VT&>(ERROR_VERTEX)){
				path.unshift(*bktracking_p);
				bktracking_p = visiter[bktracking_p->index];
			}
			
			result = FindingResult::FOUND;
		}else 
			result = FindingResult::UNREACHABLE_DEST;
		
		delete[] visiter;
		return result;
	}
	
	protected:
	virtual bool BFS(VT& v, VT** visiter, LinkedList<VT&>& searchQue) const{
		if(&v == dest) return true;
		
		for(venum_t i = 0; i < graph->getENum(); ++i) pushToQue(v, i, visiter, searchQue);
		return false;
	}
	virtual void pushToQue(VT& v, venum_t e_idx, VT** visiter, LinkedList<VT&>& searchQue) const{
		//adjacency vertex check:
		if(v.es[e_idx] == nullptr || visiter[v.es[e_idx]->index] != nullptr) return;
		//push adjacency vertex to searchQue:
		searchQue.push(*v.es[e_idx]);
		visiter[v.es[e_idx]->index] = &v;
	}
};


enum O_TurningBehavior: unsigned char{
	//正交图寻路转向行为:
	O_GO_STRAIGHT   = 0,  //直行
	O_TURN_RIGHT    = 1,  //右转
	O_TURN_AROUND   = 2,  //掉头
	O_TURN_LEFT     = 3,  //左转
	O_NO_BEHAVIOR   = 4   //无行为
};

#define O_TURNING_BEHAVIOR_EXPLAIN_0 "go straight"
#define O_TURNING_BEHAVIOR_EXPLAIN_1 "turn right"
#define O_TURNING_BEHAVIOR_EXPLAIN_2 "turn around"
#define O_TURNING_BEHAVIOR_EXPLAIN_3 "go straight"
#define O_TURNING_BEHAVIOR_EXPLAIN_4 "no behavior"


//OrthogonalPathFinder: 正交图结构寻路
template <typename VT = Vertex>
class OrthogonalPathFinder: public PathFinder<VT> {
	protected:
	using PathFinder<VT>::graph;
	using PathFinder<VT>::dest;
	using PathFinder<VT>::pushToQue;
	
	virtual bool BFS(VT& v, VT** visiter, LinkedList<VT&>& searchQue) const{
		if(&v == dest) return true;
		
		venum_t mainDirection = graph->getEIndex(*visiter[v.index], v);
		if(mainDirection != O_NONE){
			//主方向优先搜索 - 使线路尽量避免不必要的转弯
			pushToQue(v, mainDirection	 , visiter, searchQue);	
			//主方向的两边其次搜索
			pushToQue(v, mainDirection ^ 1, visiter, searchQue);
			pushToQue(v, mainDirection ^ 3, visiter, searchQue);
		}else {
			for(venum_t i = 0; i < 4; ++i) pushToQue(v, i, visiter, searchQue);
		}
		return false;
	}
	
	public:
	OrthogonalPathFinder(OrthogonalGraph<VT>& graph): PathFinder<VT>(graph) {}
	OrthogonalPathFinder(){}
	
	//获取正交图转向行为:
	static O_TurningBehavior getTurningBehavior(const VT& prev, const VT& current, const VT& next){
		venum_t currentDirection = OrthogonalGraph<VT>::getEIndex_static(prev, current),
		           nextDirection = OrthogonalGraph<VT>::getEIndex_static(current, next);
		return static_cast<O_TurningBehavior>(4 + nextDirection - currentDirection - (nextDirection < currentDirection ? 0 : 4));
	}
	O_TurningBehavior getTurningBehavior(venum_t prev_idx, venum_t current_idx, venum_t next_idx) const{
		if(graph == nullptr || prev_idx >= graph->getVNum() || current_idx >= graph->getVNum() || next_idx >= graph->getVNum()) return O_NO_BEHAVIOR;
		venum_t currentDirection = graph->getEIndex(prev_idx, current_idx),
		           nextDirection = graph->getEIndex(current_idx, next_idx);
		return static_cast<O_TurningBehavior>(4 + nextDirection - currentDirection - (nextDirection < currentDirection ? 0 : 4));
	}
	
};

}	//namespace rais


#endif
